package org.ziegler.algorithm.BFS;

import org.apache.commons.lang3.StringUtils;

import java.util.*;

/**
 * Breadth-First-Search
 * 广度优先算法
 * @author Ziegler
 * date : 2021/5/4 20:15
 */
public class Search {

    /*
    有向图
     */
    private Map<String, List<String>> graph = new HashMap<String, List<String>>();


    public static void main(String[] args) {
        Search search = new Search();
        search.init();
        search.start();
    }

    private void start() {

        LinkedList<String> searchQueue = new LinkedList<>();
        Set<String> searched = new HashSet<>();
        searchQueue.addAll(graph.getOrDefault("you", List.of()));
        while (searchQueue.size() > 0) {
            String person = searchQueue.pop();
            System.out.println("check = " + person);
            if (!searched.contains(person)) {
                if (isSeller(person)) {
                    System.out.println("person = " + person);
                    return ;
                } else {
                    searchQueue.addAll(graph.getOrDefault(person, List.of()));
                    searched.add(person);
                }
            }
        }
    }

    private boolean isSeller(String person) {
        return StringUtils.endsWith(person, "m");
    }

    void init() {
        graph.put("you", List.of("alice", "bob", "claire"));
        graph.put("bob", List.of("anuj", "peggy"));
        graph.put("alice", List.of("peggy"));
        graph.put("claire", List.of("thom", "jonny"));
        graph.put("anuj", List.of());
        graph.put("peggy", List.of());
        graph.put("thom", List.of());
        graph.put("jonny", List.of());
    }




}
